#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int N, K;
int X, A, B;

const int MAXN = 100010;

struct edge
{
    int to;
    int weight;
};

vector<edge> node[MAXN];
int cnt[MAXN];
bool vis[MAXN];
int dist[MAXN];

bool spfa()
{
    memset(dist, -0x3f3f3f3f, sizeof(dist));

    queue<int> q;
    q.push(0);
    vis[0] = true;
    dist[0] = 0;
    cnt[0] = 0;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < node[u].size(); i++)
        {
            auto temp = node[u][i];
            if (dist[temp.to] < dist[u] + temp.weight)
            {
                dist[temp.to] = dist[u] + temp.weight;
                cnt[temp.to]++;
                if (cnt[temp.to] > N)
                    return false;
                if (!vis[temp.to])
                {
                    vis[temp.to] = true;
                    q.push(temp.to);
                }
            }
        }
        vis[u] = false;
    }

    return true;
}

int main()
{
    cin >> N >> K;
    for (int i = 1; i <= K; i++)
    {
        cin >> X >> A >> B;
        if (X == 1)
        {
            node[A].push_back({B, 0});
            node[B].push_back({A, 0});
        }
        else if (X == 2)
        {
            node[A].push_back({B, 1});
        }
        else if (X == 3)
        {
            node[B].push_back({A, 0});
        }
        else if (X == 4)
        {
            node[B].push_back({A, 1});
        }
        else
        {
            node[A].push_back({B, 0});
        }
    }
    for (int i = 1; i <= N; i++)
    {
        node[0].push_back({i, 1}); //至少存在一个糖果
    }
    if (spfa())
    {
        long long ans = 0;
        for (int i = 1; i <= N; i++)
        {
            ans += dist[i];
        }
        cout << ans << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    system("pause");
    return 0;
}
